مترجم: حبیب الله علیخانی
منبع:راسخون




 

چکیده

ما یک روش مسیریابی در معماری های چیپ های شبکه ای (NoC) را آدرس دهی کردیم که در آن از روش توپولوژی های مش بندی غیر منظم با اتصال های برد بلند (LRL) استفاده می شود. این توپولوژی ها شرایط مختلف برای الگوریتم های مسیریابی را ایجاد می کنند. به عنوان یک الگوریتم استاندارد، یک ساختار استاتیک و با اتصال منظم فرض شده است و از یکسانی مش بندی های منظم به منظور جلوگیری از ایجاد بن بست و ایجاد قابلیت مسیریابی مناسب، استفاده شده است. ما یک الگوریتم مسیریابی جدید ارائه کردیم که بوسیله‌ی آن می توان این توپولوژی های غیر منظم را کپی برداری کرد و از آنها برای تعبیه کردن LRL های زمان اجرا و پیکربندی های مجدد توپولوژی استفاده کرد. روش ما برای ایجاد تطبیق در پیکربندی های توپولوژیک دینامیک، استفاده از یک روش جدید است که روابط مسیریابی را به دو مرحله تقسیم می کند: یکی محاسبه‌ی پورت های خروجی بر روی مسیر کمینه‌ی کنونی و دومی استفاده از حدهای مسیریابی برای جلوگیری از بن بست. علاوه براین، ما یک تابع گزینش ارائه کردیم که در آن از داده های توپولوژیک محلی برای انتخاب مسیر بهینه استفاده شده است.
این نشان داده شده است که الگوریتم مسیریابی بدون بن بست است. این نتیجه بعد از آنالیز تمام تصمیم گیریهای مسیریابی ممکنه در ناحیه‌ی LRL، حاصل شده است. ما نشان دادیم که این الگوریتم مسیریابی هزینه های بهینه سازی در LRL‌ را به حداقل می رساند و بهینه ترین حلقه را انتخاب می کند. وقتی این الگوزیتم بر روی LRL های دارای کمتر از 7 حلقه اعمال می شود، ترافیک کلی حلقه محاسبه شده است و از این رو مصرف انرژی کاهش می یابد. در یک شبکه‌ی 8 در 8 شبیه سازی شده، استفاده از بافر ورودی در شبکه به میزان 6.5 % کاهش یافته است.

مقدمه

چیپ های چند هسته ای و سیستم های چند پردازنده (MPSoCs) به طور روز افزون مورد استفاده قرار می گیرند و با پیشرفت این تکنولوژی، تعداد هسته های آنها در هر چیپ، افزایش می یابد. بیشتر وسایل موجود، از چند هسته استفاده می کنند اما اگر رویه‌ی کنونی ادامه یابد، چیپ های بعدی ممکن است شامل هزاران و یا صدها هسته باشند. همین طور که دانسیته‌ی اجزای این وسایل افزایش می یابد، روش های ایجاد ارتباط میان این هسته ها نیز پیچیده تر می شود. طراحی های لبه ای کنونی در چیپ های شبکه ای (NoCs) مورد استفاده قرار می گیرند و بوسیله‌ی آنها تعداد زیادی از المان های پردازش به هم متصل می شوند. این مسئله به نظر می رسد که تقریبا تمام نسل های جدید از وسایل پردازش گر با هسته های زیاد، بوسیله‌ی NoCs به هم اتصال می یابند. ایجاد مقیاس پذیری و سهولت ترکیب شدن NoC ها موجب می شود تا مزیت های زیادی برای سیستم های موازی ایجاد شود. استفاده از آنها، روش های شبکه ای و سطح مشترک هایی ایجاد می کند که بوسیله‌ی آنها اجزا در سیستم های بزرگ به راحتی، به هم متصل می شود، بدون آنکه نیازی به ایجاد برهمکنش های بیشتری باشد. این شبکه ها به طور مکرر در مقالات مورد بررسی قرار گرفته است و این بررسی ها ابتدا بوسیله‌ی Dally معرفی شدند. در برخی مقاله ها، یک مقایسه میان روش های باس، نقطه به نقطه و NoC بیان شده است.

طراحی NoC رایج

دو حالت اصلی مورد علاقه وقتی است که طراحی NoC ها به صورت مسیری و برای بررسی کارایی باشد و دومین حالت توپولوژی اصولی و الگوریتم های مسیریابی مربوط به آن می باشد که برای تسهیل انتقال داده مورد استفاده قرار می گیرد. بسیاری از طراحی های روتوری با کارایی بالا، موجود می باشند: برای مثال، طراحی دروازه ای ساعتی و سیگنالی بوسیله‌ی Mullins مورد بررسی قرار گرفته است. همچنین در مقاله های دیگر، روشی برای استخراج مدل های انرژی برای روتورها ارائه شده است. طراحی های دیگری نیز در مقاله های دیگر، معرفی شده است اما این بررسی این طراحی ها، هدف این مقاله نمی باشد. به هر حال، ما علاقه داریم تا در مورد جزء ثانویه صحبت کنیم. بیشتر کارهای انجام شده بر روی الگوریتم های مسیریابی، تنها شبکه های با توپولوژی یکنواخت را در نظر گرفته اند( عموما یک مش دو بعدی). سایر کارها ساختارهای سه بعدی را توسعه داده اند مثلا tori ، از اتصال های وراپوند برای توسعه‌ی بدون بعد لبه های شبکه و هایپرکیوب، استفاده کرده است.
تحقیق کنونی همچنین موضوعات مرتبط با مسیردهی فرایند به هسته را آدرس دهی می کند. برای این کار، فرایندهای زیادی وجود دارد که بوسیله‌ی آنها تکنیک های مسیردهی و زمان بندی ، ایجاد می شود. مسیردهی فرایند به هسته‌ی مؤثر استفاده از یک توپولوژی شبکه ای ثابت را بهینه سازی می کند. به هر حال، مسئله‌ی متضمن Np-hard است. بنابراین اگر مسائل همگی قابل حل باشند، ابتکارات ذهنی باید مورد استفاده قرار گیرد. تابکاری شبیه سازی شده یکی از این مثال هاست. علاوه براین، این تکنیک ها تنها برای شبکه های استاتیک قابل استفاده هستند زیرا آنها آنالیز استاتیک زمان کامپایلی را اجرا می کنند که نمی تواند در هنگام ایجاد تغییرات زمان اجرا در سطح مشترک اتصال داخلی، محاسبه شود. بیشتر این تکنیک ها محدودیت های عمده ای دارند. مثلا زمان اجرا از چند دقیقه تا چند ساعت طول می کشد و این مسئله موجب می شود تا از استفاده‌ی عملی از آنها در کاربردها جلوگیری شود.

نسل جدید NoC ها

انتخاب توپولوژی مهمتر از انتخاب طراحی روتور است زیرا توپولوژی کوتاه ترین راه ها در شبکه را پیدا می کند. توپولوژی هایی که به طور کامل به کاربرد مورد نظر، مسیردهی شده اند، موجب ایجاد سیستم های مؤثر می شوند و ما به طورفزاینده ای، تحقیقاتی را می بینیم که در آنها خلا کاربردی میان توپولوژی های غیر انعطاف پذیر مخصوص یک کاربرد و NoC های با اهداف عمومی به طور کامل پوشش دهی می شود. Ogras و Marculescu یک معماری و روش معرفی کرده اند که بوسیله‌ی آن یک توپولوژی بهینه ایجاد می شود. با اجرای آنالیز بر روی فرکانس و دامنه‌ی ارتباط میان المان های پردازش برای یک کاربرد خاص، نویسندگان محل بهینه ای را محاسبه کرده اند که در آن اتصال های بلند برد با یک مش استاندارد، ایجاد می شود. سپس یک NoC با اتصال بهینه‌ی بلند برد ایجاد می شود. یک الگوریتم مسیریابی بدون بن بست ارائه شده است که از توپولوژی غیر منظم حمایت می کند و روشی برای آنالیز کاربردهای مد نظر می باشد. مبانی موجود نشان می دهد که بار بحرانی تا 18.7 افزایش می یابد و تأخیر بسته ای متوسطی برابر با 69% در مش 10 در 10، ایجاد می شود. تکنیک ضمیمه شده به یک آنالیز کاربردی استاتیک دوره ای وابسته است و در نهایت یک NoC منفرد، و با کارایی ویژه ایجاد می کند. این تکنیک دارای یک توپولوژی ثابت است اما این نشان داده شده است است که این تکنیک در شبکه های با مش بندی غیر منظم کارایی دارد.
معماری های NoCبا قابلیت طراحی مجدد مثالی دیگر از مزیت های یک توپولوژی غیر منظم است. یک تسهیم کننده در اطراف هر روتور قرار داده شده است و به گونه ای طراحی شده تا هر ورودی بتواند به طور مستقیم به هر خروجی مسیردهی شود. این کلید T همچنین اجازه‌ی پایپلینگ فلیت ها ( یعنی افزایش سرعت پردازش) را می دهد به نحوی که ساعت های اتصال های منفرد تحت تأثیر قرار نمی گیرند. بسته ها مسیردهی می شوند بدون اینکه بافر یا سوئیچی داشته باشند و توپولوژی های خاص کاربرد می تواند محاسبه شوند و در میان اجرای کار، پیکربندی شوند. در این سیستم ها، صرفه جویی انرژی 56 % مشاهده شده است و تنها 10 % از اوورهد مساحت (area overhead) در این سیستم مشاهده شده است. به هر حال، آنالیز استاتیک جریان های ترافیکی برای پیکربندی توپولوژی اولیه مورد نیاز است.
ما دیده ایم که اضافه کردن بی نظمی به شبکه ها می تواند کارایی آنها را در زمانی که سیستم های نسل بعدی توسعه می یابند، می تواند بهبود یابد. علاوه بر این، قابلیت اضافه کردن دینامیک یک چنین اتصال هایی، به شرایط ترافیک زمان اجرا بستگی دارد.این مسئله یکی از ویژگی های بسیار مناسب برای نسل های جدید NoC هاست. بیشتر کارهای موجود در زمینه‌ی NoCها بر اساس توپولوژی های منظم انجام شده است که این توپولوژی ها ممکن است به طور آماری مورد ارزیابی قرار گیرند تا بتوان میزان فیت شوندگی آنها با کاربردهایشان، تعیین گردد. ما اعتقاد داریم که این شبکه بسیار انعطاف پذیر است و به ما اجازه می دهد تا NoC های با پیکربندی های مؤثری را برای محیط های محاسباتی با اهداف عمومی، توسعه دهیم. به جای ایجاد بهینه سازی ها برای کدگذاری، سیستم های دینامیک اجازه‌ی بهینه سازی برای کد گذاری قراردادی را پیش از آنالیز، می دهد. این مسئله در بسیاری از مثال ها، گران بهاست (برای مثال، در سیستم هایی که کدگذاری بوسیله‌ی کاربر در هر زمانی قابل اجراست یا در جاهایی که بخش های غیر قابل پیش بینی از کدها مورد استفاده قرار می گیرد). در این سناریوها، این مهم است که نوع آنالیز استاتیک اعمال شده به سیستم های پردازش، نمایش داده شود؛ زیرا این اطلاعات در راه اندازی موجود نمی باشند. ما اعتقاد داریم که سیستم های بعدی دارای انعطاف پذیری بیشتری هستند و نسبت به سیستم های کنونی، قابلیت استفاده‌ی مجدد دارند و بنابراین، قابلیت اجرای زمان بندی فرایند استاتیک و مسیر دهی، قابل حصول نمی باشد. ما در این زمینه تنها نیستیم و این واقعیت ها از توسعه‌ی سیستم های با قابلیت طراحی مجدد دینامیک، نشئت می گیرند. اولین مرحله از این کار، احتمالا بهینه سازی دینامیک NoC در زمان اجراست و بوسیله‌ی آن، اجازه داده می شود تا NoC از جریان های ترافیک ایجاد شده در آن، استفاده کند. وقتی این مسئله اتفاق افتد، یک پیش نیاز ضروری برای عملیات تصحیح، آگاهی یافتن و توسعه‌ی الگوریتم مسیریابی برای حمایت از این اجراست. دراین مقاله، ما تنها این مسئله را در نظر گرفتیم که: چگونه مسیرهای امن و مؤثر در یک شبکه ایجاد می شود. در واقع در این شبکه، LRL ها می توانند مسائل غیر منتظره‌ی ایجادشده در حین اجرا را تخریب کنند. کار قبلی ما شرایط شبکه ای را در نظر گرفته بود که تحت آن شرایط، قرار دادن این نوع از اتصال ها بهینه باشد و از این رو، ما بر روی نحوه‌ی تصدیق مسیر در یک شبکه صحبت می کنیم.

اجرای LRL های موجود

افزودن LRL ها به شبکه موجب ایجاد بی نظمی در ساختار شبکه می شود. این بی نظمی ها تمایل دارند تا شبکه را از لحاظ مسیردهی نیازمندی های کاربردی دقیق تر کند. این مسیردهی ها در پردازش های مختلف المان هایی که به هم متصل شده اند، اجرا می شوند. این شکل از بهینه سازی ایجاد شبکه های بی نظم با شکل صحیح را در حالتی استاندارد میسر می کند. به هر حال، بی نظمی همچنین آنالیز شبکه را پیچیده می کند و به طور خاص، الگوریتم مسیریابی را نیز پیچیده می کند. شبکه های بی نظم همچنین می تواند با ایجاد خطا در شبکه های منظم نیز ایجاد می شوند. این یک زمینه‌ی مجزا اما مرتبط با موضوع ماست زیرا بیشتر کار موجود بر روی شبکه های غیر منظم بر اساس فرض هایی است که در آن شبکه نظم خود را از دست می دهد. با استفاده از مسیردهی وظیفه به هسته و توپولوژی ثابت، ReNoC چالش های مسیریابی جدید ایجاد نمی کند. پیکربندی های ممکنه به خاطر فقدان وجود یک الگوریتم مسیریابی مخصوص برای شبکه های با مش بندی غیر منظم، محدود می شوند. تعبیه‌ی اتصال با برد بلند برای توسعه‌ی یک روش مسیریابی جدید مورد نیاز هستند. بواسطه‌ی این روش، اطمینان حاصل می شود که این اتصال ها به طور مؤثر مورد استفاده قرار گرفته اند و از بوجود آمدن بن بست در این ساختارها نیز جلوگیری شده است.
آدرس دهی صحیح چالش های مسیریابی می تواند سایر مزیت ها مانند قابلیت ایجاد یک میزان مناسب از انحراف و خطا، را نیز ایجاد کند. یک مثال از الگوریتم مسیریابی تنظیم شده برای این فضا، الگوریتم مسیریابی خطا- نوسان است که بوسیله‌ی Chen معرفی شده است. این الگوریتم در برخی مقاله ها مورد بررسی قرار گرفته است. تغییر منطقی در توپولوژی بوسیله‌ی افزودن توابع اضافی به روتور مانند کانال های با بیان صریح (EVCs)،‌ قابل بررسی است. EVCs یک روش جدید برای کنترل جریان است که به بسته ها اجازه می دهد به طور مجازی از روتورهای منفردعبور کنند. این کار با اتصال استاتیک یک کانال مجازی در یک روتور به یک کانال در روتور دیگر قابل انجام است و به این EVCs ایجاد شده یک حق تقدم نسبت به VCs استاندارد می دهد. نتایج ارائه شده نشان می دهد که مصرف انرژی در این حالت 38 % کاسته می شود و تأخیر زمانی بسته نیز 84 % کاهش می یابد.
در این مقاله، ما مسئله‌ی تحقق یک نوع مشابه از توپولوژی دینامیک را در نظر گرفتیم اما بر روی دینامیک فیزیکی تمرکز کرده ایم نه دینامیک منطقی. سناریوی ما آدرس دهی وضعیت هایی است که در آن LRLها ممکن است به طور دینامیک به شبکه افزوده شود و بدین وسیله، کارایی محاسباتی آن بهبود می یابد. این شبکه ها این عملکرد را ارائه می دهند در حالی که میزان افزایش پیچیدگی روتور را در یک روتور با مش بندی اولیه، مینیمم می کند. ما بحثمان را به اجراهایی محدود می کنیم که در انها LRL در طول سطرها یا ستون ها اضافه شده است (شکل1). هدف کلی محدود کردن اوورهد LRL با استفاده‌ی مجدد از پورت ها و سیم های روتور موجود می باشد. تحت این مکانیزم، به جای افزوده شدن پورت اضافی به هر روتور متصل به LRL، یک اتصال حلقه ای منفرد به هر روتور متصل به LRL است. در این حالت یک اتصال حلقه ای منفرد به صورت ساده با LRL جایگزین می شود(شکل 1). ما این حالت را به اشتراک گذاشتن LRL‌ می نامیم. این مسئله موجب کاهش پیچیدگی روتور می شود اما موجب تغییر توپولوژی شبکه می شود. این تغییر آن دسته از اتصال های حلقه ای را که در طول یک مسیر LRL, واقع شده اند را غیر فعال می کنند. وقتی یک روتور دارای یک گردش LRL در این حالت است، ایجاد مسیر فرعی بوسیله‌ی این اتصال، مؤثر می باشد. برای مثال، در شکل 1، پرت جانبی شرقی غیر فعال می شود و هیچ ترافیکی قادر به رسیدن به پورت وردی غربی نیست. فرض های ما از فرض های در نظر گرفته شده بوسیله‌ی Ogras و همکارانش متفاوت است.
یکی از اولین برسی ها نشان داده که تفاوت اندکی میان الگوریتم مسیریابی مورد نیاز برای حمایت از شبکه های نوسان خطا(FT) و شبکه های با توپولوژی دینامیک(DT) وجود دارد. به هر حال، برخی تفاوت های عملی وجود دارد. از این مهمتر، وقتی توپولوژی به یک درجه‌ی معین تغییر کند، این انتظار وجود دارد که الگوریتم FT با ایجاد جفت های منبع- مقصد غیر قابل روت شدن یا ایجاد بن بست، شکست می خورد. یک بخش بزرگ از تحقیق در زمینه‌ی الگوریتم های FT که بر اساس عدد و الگوی خطای ایجاد شده در هر الگوریتم، پایه گذاری شده اند، می توانند تحت حمایت قرار گیرند. یک الگوریتم طراحی شده بر پایه‌ی شبکه‌ی DT هیچ وقت شکست نمی خورد. زیرا این توپولوژی با توجه به قیود قراردادی، دوباره پیکربندی می شوند. علاوه بر این، خطاها عموما موجب ایجاد تغییرات دائمی در شبکه ای می شود که پیکربندی مجدد دینامیک آن به طور برگشت پذیر، طراحی شده اند. به دلیل طبیعت این ساختار، خطاها قابل پیش بینی و مقید کردن، نیست. این مسئله بر روی هر بخش از شبکه اثر می گذارد. پیکربندی های مجدد دینامیک در الگوریتم های تعریف شده وبا توجه به گروه پارامتری، ایجاد می شود. و تفکیک کردن شبکه به ناحیه هایی که ممکن است به طور دینامیک پیکربندی شوند ویا نشوند، ساده است. یک تفاوت دیگر نیاز به تشخیص تشخیص خطا، آگاهی در مورد بسته ها، اتلاف ها و ارسال مجدد می باشد. یک چنین مکانیزمی در شبکه های با پیکربندی مجدد و دینامیک، ضروری هستند.
بخش های بعدی بر روی ساخت یک الگوریتم مسیریابی بدون بن بست، تمرکز دارد. این الگوریتم از شبکه های خود بهینه ساز حمایت می کنند و در آنها می توان LRLها را در زمان اجرا، اضافه یا کم کرد. این کار با توجه به خصوصیت های بار دینامیک انجام می شود. این مقاله فرض کرده است که یک چنین شبکه‌ی خود بهینه ای وجود دارد و به واقعی بودن آن کار ندارد. ترجیحا ما مشکلات مسیریابی در یک چنین شبکه ای را آدرس دهی کردیم. ما هم اکنون میزان صرفه جویی در مصرف و کاهش تأخیرهای زمانی را در چنین معماری هایی، نشان داده ایم. ما اکنون روش های طراحی الگوریتم مسیریابی را قبل از ساخت الگوریتم مسیریابی جدید خود (Opt-bypass)، مورد بررسی قرار دادیم.

تعاریف

در این بخش، ما واژه های کلیدی را تعریف کردیم که در این مقاله مورد استفاده قرار دادیم. مسیر بهینه‌ی منظم اشاره به مسیری بهینه بر روی ساختار مش بندی یکنواخت می باشد(بدون در نظر گرفتن پورت ها یا LRL ها. مسیر بهینه‌ی غیر منظم به مسیربهینه ای اشاره دارد که محل LRL و پورت های خروجی غیر فعال شده را در نظر می گیرد. در شکل 1، روتور R2 یک مسیر بهینه‌ی منظم از R1 به R3 است اما به دلیل وجود LRL، این مسیر غیر منظم نیست. در مورد توپولوژی های غیر یکنواخت، عدد حلقه میان دو گره می تواند بزرگتر یا کوچکتر از فاصله‌ی Manhattan است. علاوه بر این، عدد حلقه میان گره ها می توانند در طی زمان تغییر کنند. این تغییر زمانی انجام می شود که جایگزین های دینامیکی در نظر گرفته شده باشد. ما استدلال های بخش بعدی را درنظر گرفتیم. در این استدلال ها، ما بر روی مسائل خاص بحث کردیم. این مباحث خاص با استدلال های توپولوژیکی مان معرفی شده اند. یک سد در برابر مسیریابی، به پورت خروجی اشاره دارد که در حالت دیفالت وجود ندارند و از مسیریابی در طول مش بندی یکنواخت جلوگیری می کنند. یک پورت مسدود شده دارای قابلیت اتصال ویا انفصال از LRL‌ است. ما از روتور مسدود شده برای اشاره به روتوری استفاده می کنیم که در آن، بسته به عنوان مانعی در برابر مسیریابی می شود و روتور ارسال کننده به روتوری اشاره دارد که بسته ها را پیش از روتور مسدود شده، انتقال می دهد. یک چرخش ترمینالی نشاندهنده‌ی چرخشی غیر صفر یک بسته است.

مسیریابی در شبکه های غیر منظم

یک جزء کلیدی در یک شبکه‌ی با اتصال داخلی، الگوریتم مسیریابی است. زیرا این بخش مسیری را تعیین می کند که هر بسته از منبع تا مقصد آن را پیگیری می کند. یک الگوریتم مسیریابی خوب، تأخیر زمانی بسته را مینیمم می کنند و می توان شبکه ای بدست آورد که عملکرد ان بهینه است. این درحالی است که از تجمع روتورها یا اتصال های منفرد جلوگیری می شود. در طراحی NoC، این مناسب است که الگوریتم مسیریابی با سهولت اجرا شود طوری که اثر شبکه بر روی هزینه های کلی چیپ مینیمم شود. در این شرایط، الگوریتم های مسیریابی در نظر گرفته شدند.

الگوریتم های مسیریابی بر پایه‌ی فراموشی

در فضای الگوریتم های مسیریابی بر پایه‌ی فراموشی، مسیریابی با ابعاد منظم (DOR) ، انتخاب متداول است. البته این مسئله در حالی است که ویژگیهای تعادل بار در این الگوریتم ها ضعیف است زیرا شرایط شبکه اثری بر تصمیم گیریهای مسیریابی ندارد. الگوریتم های مسیریابی فراموشی استاندارد یک رابطه‌ی مسیریابی(R) به شکل زیر دارد:

و بدین صورت، یک کانال خروجی ( C_out) از گروه کانال های C برای یک جریان معین و گره مجزا از گروه گره های N، انتخاب می شود. چون شرایط شبکه در نظر گرفته نشده است و تنها یک ایده‌ی خروجی منفرد وجود دارد، کارایی یک الگوریتم مسیریابی فراموشی محدود می شود.
مسیریابی بر روی NoC های با مش بندی غیر منظم در مقاله ای دیگر در نظرگرفته شده است اما این بی نظمی ها نتیجه ای از اندازه‌ی المان های پردازش غیر یکنواخت است و موجب ایجاد برخی اتصال ها و از بین رفتن برخی دیگر می شود. بنابراین، این بی نظمی ها طبیعتا استاتیک هستند و یک طول اتصال غیر یکنواخت در نظر گرفته نشده است. یک روش شناسی برای پیکربندی مجدد شبکه‌ی استاتیک ودینامیک دارای عملکرد مسیریابی استاتیک است اما ممکن است در زمان اجرا با روشی دیگر جایگزین شود. این مسئله یک مکانیزم بدون بن بست برای سوئیچینگ شبکه در کل تابع مسیریابی جدید، فراهم می آورد که بوسیله‌ی آن، اجزای شکسته یا نیازمند جایگزینی، جابجا می شوند. در حالی که این کار یک مقدار بزرگ از تجمع را در شبکه ایجاد می کند، ما یک الگوریتم مسیریابی منفرد را برای حمایت از الحاق دینامیک و زدایش LRL توصیف شده، در نظر گرفته ایم. سهم ما مهیا نمودن یک الگوریتم مسیریابی سازگار است که بوسیله‌ی آن از شبکه های با مش بندی غیر منظم، حمایت می شود. این مسئله از پیکربندی مجدد دینامیک نشئت می گیرد.

الگوریتم های مسیریابی انطباقی

الگوریتم های مسیریابی انطباقی می تواند از اطلاعاتی در مورد حالت شبکه استفاده کند و بوسیله‌ی آنها چندین مسیر جایگزین انتخاب کند. این کار این اطمینان را حاصل می کند که بسته ها بر روی پورتهای خروجی غیر قابل دسترس، بلوکه نشده باشند و این بسته ها در حول بی نظمی های ایجاد شده در توپولوژی، جهت دهی می شوند. یک ارزیابی از الگوریتم های مسیریابی گودال کرمی در مقاله ای دیگر، ارائه شده است.
الگوریتم های مسیریابی کاملا انطباقی به هر بسته اجازه می دهد تا از هر مسیر کوتاهی میان منبع و مقصد استفاده کند. یک الگوریتم با انطباق جزئی تنها اجازه می دهد تا یک بسته از یک زیر گروه از مسیرهای بهینه،استفاده کند. یک الگوریتم مسیریابی انطباقی شامل دو جزء است: یک رابطه‌ی مسیریابی و یک تابع انتخاب. رابطه‌ی مسیریابی به یک گروه از کانال های خروجی از باز می گردد. این کانال ها پر توان ترین کانال ها برای یک گره کنونی و مقصد از N هستند:

کانال ورودی می تواند همچنین به عنوان یک اضطرار برای کانال های خروجی در نظر گرفته شود:

الگوریتم مسیریابی Opt-y بوسیله‌ی Schweibert و Jayasimha معرفی شد. این یک الگوریتم کاملا انطباقی است و نویسندگان نشان دادند که این الگوریتم نیازمند حداقل قیود و کانال های مجازی برای هر الگوریتم کاملا انطباقی ( برای شبکه های مش بندی شده) هستند. ما از Opt-y به عنوان الگوریتم های مسیریابی پایه استفاده می کنیم. تغییرات ما بسیار قابل توجه است اما رد غیاب LRL، الگوریتم ما به طور ایده آل به Opt-y عمل می کند. برای انتخاب کانال خروجی از گروه بازگشتی بوسیله‌ی R، یک تابع انتخاب باید به صورت زیر تعریف شود:

که در اینجا، کانال خروجی است که در بسته قرار داده شده است. انتخاب تابع انتخاب بوسیله‌ی Schweibert و همکارانش نشان داده شده است. این تابع دارای اثر قابل توجهی بر روی زمان تأخیر متوسط و رفتار اشباع شوندگی الگوریتم های مسیریابی انطباقی دارد. نویسندگان عدد توابع انتخاب را با استفاده از Opt-y ارزیابی کردند و نشان دادند که در بیشتر موارد، بهترین انتخاب تابع No-turn است. این تابع که بوسیله‌ی Dally ارائه شده است، این اطمینان را حاصل می کند که یک بسته وقتی تمام کانال های چرخشی صفر، بلوکه شده اند، تنها از جهت کنونی اش، مشتق می گیرد. دراین حالت، عدد ستون ها و سطرهای یک بسته حداقل می شود. در کل، تابع No-turnدارای کمترین میزان پیکربندی و تأخیر زمانی است.

مسیریابی بدون بن بست

بن بست زمانی ایجاد می شود که یک فلیت یا بسته منتظر منبعی است که هرگز آزاد نمی شود. این مسئله می تواند موجب خنثی شدن یک برهمکنش در شبکه شود. برای مهاجرت این بسته، این اطمینان باید حاصل گردد که وابستگی های منبع ایجاد کننده‌ی بن بست نتواند ایجاد گردد و یا از روش هایی برای تشخیص و بازگردانی بن بست ها استفاده کند. مثال های زیادی از هر کدام در مقالات آورده شده است اما در این مقاله، دغدغه‌ی ما بیشتر جلوگیری از بوجود آمدن بن بست های ایجاد شده در شبکه هاست. این کار با استفاده از همپوشانی LRL ها انجام می شود. بیشتر الگوریتم های بر پایه‌ی ساختار یکنواخت استاتیک پایه گذاری شده اند و موجب می شوند تا شبکه‌ی متضمن خالی از بن بست باشد و این اطمینان حاصل شود که یک بسته می تواند برای هر جفت منبع- مقصد، مسیردهی شود. نه تنها ما یک توپولوژی غیر منظم را در نظر گرفتیم، بلکه همچنین متوجه شدیم که بی نظمی های موجود با زمان و شرایط ترافیکی تغییر می کنند.
کانال های مجازی(VCs) می تواند برای جلوگیری کردن از بروز بن بست مورد استفاده قرار گیرد. یک VC دارای بافر مخصوص به خود است اما پیام ها را با استفاده از کانال فیزیکی مشترک تسهیم می کند. وقتی یک بسته در یک VC بلوکه شود، کانال فیزیکی می تواند هنوز بوسیله‌ی بسته های موجود در سایر کانال های مجازی مورد استفاده قرار گیرد. Dally و Seitz نشان دادند که یک رابطه‌ی مسیریابی فراموشی که در معادله‌ی دوم آورده شده است، بدون بن بست است اگر، هیچ سیکلی در گراف وابستگی کانال آن(D) وجود نداشته باشد. این گراف مستقیم به نحوی ساخته شده است که هر راس یک VC در شبکه است و هر لبه یک جفت از کانال های مجازی اتصال یافته از طریق رابطه‌ی مسیریابی است. این بعدا نشان داده می شود که الگوریتم های مسیریابی فراموشی ممکن است شامل سیکل هایی باشد اما هنوز هم بدون بن بست باشد. Glass و Ni یک مدل چرخشی معرفی کردند که در آن سیکل های بن بستی با استفاده از وابستگی های کانالی یا لزوم ایجاد چرخش در ساخت آنها، توصیف شده اند. پس با محدود کردن برخی چرخش ها، اطمینان حاصل می شود که بن بست در آنها ایجاد نمی شود. محدود کردن چرخش یک نظم در کانال های شبکه ایجاد می کند. بن بست از ایجاد اطمینان در زمینه‌ی دستیابی تمام کانال ها به بسته ها، جلوگیری می کند. این مسئله با افزایش یا کاهش قابل توجه در نظم همراه است.
Duato نتایج کلیدی ارائه کرده است و مطابق با چیزی که Dally می گوید، او نیز نشان داده است که امکان ساخت الگوریتم های مسیریابی بدون بن بست به شکل معادلات سوم و چهارم وجود دارد. این معادلات هنوز هم دارای سیکل هایی است. با اطمینان حاصل کردن از این مسئله که بسته ها دارای مسیرهای سیکلی دیگری هستند و همچنین بطور نامحدود برای منابع مشغول انتظار نمی کشند، این سیکل قابل دستیابی نیست و می توان از آن ها جلوگیری کرد. ما از این نتایج استفاده می کنیم تا بعدا و در بخش بعدی نشان دهیم که الگوریتم مسیریابی انطباقی ما برای شبکه های دارای LRL، بدون بن بست هستند.

بدون بن بست شدن

در روش های موجود که در بخش بعدی بدان اشاره شد، توپولوژی ها ممکن است بی نظم باشند اما شکل آنها بعد از مقدار دهی، ثابت است.
برخلاف تمام کارهای گذشته، روش ما شبکه هایی را در نظر گرفته است که در آنها توپولوژی به صورت دینامیک تغییر می کند. با در نظر گرفتن قیود تعریف شده، اکنون، هیچ روش کلی برای جلوگیری وجود ندارد که بوسیله‌ی ان یک الگوریتم مسیریابی برای توپولوژی با قابلیت پیکربندی مجدد بدون بن بست باشد؛ زیرا توپولوژی می تواند تغییر کند و بنابراین امکان ایجاد وابستگی کانالی وجود دارد. در این حالت امکان حذف و یا اضافه شدن یک کانال وجود دارد. به هرحال، در بخش بعدی، ما یک مشارکت کلی انجام دادیم که بوسیله‌ی آن نشان داده می شود الگوریتم ما بدون بن بست است. برای انجام این کار، ما کارهای زیر را انجام می دهیم:
تصدیق این موضوع که این الگوریتم بدون بن بست است و در توپولوژی های با مش یکنواخت کارایی دارد
برشمردن چرخش های اضافی که برای حفظ مسیریابی در زمان های تغییر توپولوژی، مورد نیاز است.
نشان دادن این موضوع که این چرخش ها بر روی اثبات اولیه، اثر ندارد.
ما این مسائل را در بخش های بعدی اعمال کرده ایم زیرا ما این روش جدید را برای مسائل مطرح شده در زمینه‌ی توپولوژی های دینامیک غیر منظم، مورد استفاده قرار دادیم (شکل 2).

روش ما: یک الگوریتم مسیریابی دینامیک جدید

ما اکنون در مورد Opt-bypass صحبت می کنیم. الگوریتم مسیریابی جدید ما برای مواقعی طراحی شده است که در آن، LRL در توپولوژی مش بندی شده ای تعبیه شده است که حالت آن در بخش اول توصیف شده است. اولا، ما نیازمندی های عمومی مورد نیاز برای Opt-bypass را بیان کرده ایم و همچنین قیود موجود در آن را بیان کرده ایم. ما سپس جزئیات که بوسیله‌ی ان این الگوریتم از عهده‌ی بی نظمی ها بر می آید را معرفی کردیم و سپس نحوه‌ی عمل آنها را تحت سناریوهای مختلف مورد بررسی قرار دادیم.

/ج